Fast dictionary search and maintenance are becoming important to deal with “big data”. Many big data applications require not only large data handling, but also supporting massive continuous updates (insertion, deletion) and search requests including longest common prefix (LCP) matching and range queries. Therefore, it is very important to develop methods to store data with very fast search and update capability. Family of search tree (e.g., binary search tree, or B+ tree) has been used in many database management systems, but those methods are becoming too slow and expensive for big data applications. Distributed hashing methods are used in many big data management systems for speed and scalability, but hashing based systems have very large time penalties for operations like range query. Family of trie including PATRICIA trie have been known to have good theoretical running times for dictionary operations, but run very slowly in practice due to many random memory accesses needed.
The figures depict various embodiments of the present disclosure for purposes of illustration only. One skilled in the art will readily recognize from the following discussion that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the disclosure described herein.